﻿#ifndef __HASH_TABLE_HPP__
#define __HASH_TABLE_HPP__

#include <vector>
#include <utility>
#include <string>

namespace SFW
{
    using std::vector;
    using std::pair;
    using std::string;
    using std::size_t;

    // 默认哈希函数(这个作用将不同类型转换为size_t类型)
    template<class K>
    struct DefaultHashFunc
    {
        size_t operator()(const K& key)
        {
            return (size_t)key;
        }
    };


    template<>
    struct DefaultHashFunc<std::string>
    {
        size_t operator()(const std::string& str)
        {
            size_t hash = 0;
            for (auto ch : str)
            {
                hash *= 131;
                hash += ch;
            }

            return hash;
        }
    };

// --------------------------------------------hash table-------------------------
    // 哈希表的节点
    enum class STATE
    {
        EXIST, // 存在
        EMPTY, // 不存在
        DELETE // 删除
    };

    template<class K, class V>
    struct HashData
    {
        pair<K, V> m_kv;
        STATE m_state = STATE::EMPTY;
    };


    template<class K, class V, class HashFunc = DefaultHashFunc<K>>
    class HashTable
    {
    private:
        vector<HashData<K, V>> m_table;
        size_t m_size;

    public:
        HashTable(size_t capacity = 10);
        // 插入
        bool insert(const pair<K, V>& kv);
        // 查找
        HashData<const K, V>* find(const K& key);
        // 删除
        bool erase(const K& key);
        
        size_t size() const {return m_size;};
    };

    template<class K, class V, class HashFunc>
    HashTable<K, V, HashFunc>::HashTable(size_t capacity)
            :m_table(capacity)
            ,m_size(0)
    {}

    template<class K, class V, class HashFunc>
    bool HashTable<K, V, HashFunc>::insert(const pair<K, V>& kv)
    {
        // 1. 负载因子超过0.7，扩容
        if(m_size * 10 / m_table.size() >= 7)
        {
            size_t newCapacity = m_table.size() * 2;
            HashTable<K, V, HashFunc> newTable(newCapacity);
            // 扩容后，映射关系改变
            for(size_t i = 0; i < m_table.size(); ++i)
            {
                if(m_table[i].m_state == STATE::EXIST)
                {
                    newTable.insert(m_table[i].m_kv);
                }
            }
            m_table.swap(newTable.m_table);
        }
        // 2. 使用哈希函数计算哈希值
        HashFunc hash;
        size_t hashi = hash(kv.first) % m_table.size();
        // 3. 哈希冲突，采用线性探测
        while(m_table[hashi].m_state == STATE::EXIST)
        {
            // 如果存在,则更新
            if(m_table[hashi].m_kv.first == kv.first)
            {
                m_table[hashi].m_kv.second = kv.second;
                return true;
            }
            ++hashi;
            hashi %= m_table.size();
        }
        // 4. 插入
        m_table[hashi].m_kv = kv;
        m_table[hashi].m_state = STATE::EXIST;
        ++m_size;
        return true;
    }

    template<class K, class V, class HashFunc>
    HashData<const K, V>* HashTable<K, V, HashFunc>::find(const K& key)
    {
        // 1. 使用哈希函数计算哈希值
        HashFunc hash;
        size_t hashi = hash(key) % m_table.size();
        // 2. 哈希冲突，采用线性探测
        while(m_table[hashi].m_state != STATE::EMPTY)
        {
            if(m_table[hashi].m_state == STATE::EXIST && m_table[hashi].m_kv.first == key)
            {
                return (HashData<const K, V>*)&m_table[hashi];
            }
            ++hashi;
            hashi %= m_table.size();
        }
        return nullptr;
    }

    template<class K, class V, class HashFunc>
    bool HashTable<K, V, HashFunc>::erase(const K& key)
    {
        // 如果选择真的删除数据
        // 1. 使用哈希函数计算哈希值
        // HashFunc hash;
        // size_t hashi = hash(key) % m_table.size();
        // while(m_table[hashi].m_state != STATE::EMPTY)
        // {
        //     if(m_table[hashi].m_state == STATE::EXIST && m_table[hashi].m_kv.first == key)
        //     {
        //         // 需要重新排序, 效率低下
        //     }
        // }
        // 

        HashData<const K, V>* dataPtr = find(key);
        if(dataPtr != nullptr)
        {
            dataPtr->m_state = STATE::DELETE;
            --m_size; // 注意size-1
            return true;
        }
        return false;
    }


//------------------------------------------------hash桶-----------------

    // 哈希桶上链表的节点
    template<class K, class V>
    struct HashNode
    {
        HashNode()
            :m_next(nullptr)
        {}

        HashNode(const pair<K, V>& kv)
            : m_kv(kv)
            , m_next(nullptr)
        {}

        pair<K, V> m_kv;
        HashNode<K, V>* m_next;
    };

    template<class K, class V, class HashFunc = DefaultHashFunc<K>>
    class HashBucket
    {
    private:
        vector<HashNode<K, V>> m_bucket;
        size_t m_size;
    public:
        HashBucket(size_t capacity = 10);
        // 插入
        bool insert(const pair<K, V>& kv);
        // 查找
        HashNode<const K, V>* find(const K& key);
        // 删除
        bool erase(const K& key);

        size_t size() const {return m_size;};
    };

    template<class K, class V, class HashFunc>
    HashBucket<K, V, HashFunc>::HashBucket(size_t capacity)
        : m_bucket(capacity)
        , m_size(0)
    {}

    template<class K, class V, class HashFunc>
    bool HashBucket<K, V, HashFunc>::insert(const pair<K, V>& kv)
    {
        // 负载因子为1时扩容
        if(m_size == m_table.size())
        {
            int newCapacity = m_table.size() * 2;
            vector<HashNode<K, V>> hashBucket(newCapacity);
            

        }
        // 1. 计算hash值
        HashFunc hash;
        size_t hashi = hash(kv.first) % m_bucket.size();
        // 2. 插入
        HashNode<K, V>* newNode = new HashNode<K, V>(kv);
        newNode = m_bucket[hashi].m_next;
        m_bucket[hashi].m_next = newNode;
        m_size++;
        return true;
    }

    template<class K, class V, class HashFunc>
    HashNode<const K, V>* HashBucket<K, V, HashFunc>::find(const K& key)
    {
        // 1. 计算hash值
        HashFunc hash;
        size_t hashi = hash(key) % m_bucket.size();
        // 2. 遍历链表
        HashNode<K, V>* cur = m_bucket[hashi].m_next;
        while(cur)
        {
            if(cur->m_kv.first == key) 
                return (HashNode<const K, V>*)cur;
            cur = cur->m_next;
        }
        return nullptr;
    }

    template<class K, class V, class HashFunc>
    bool HashBucket<K, V, HashFunc>::erase(const K& key)
    {
        // 1. 计算hash值
        HashFunc hash;
        size_t hashi = hash(key) % m_bucket.size();
        // 2. 遍历链表
        HashNode<K, V>* cur = m_bucket[hashi].m_next;
        HashNode<K, V>* prev = &m_bucket[hashi];
        while(cur)
        {
            if(cur->m_kv.first == key) 
            {
                prev->m_next = cur->m_next;
                delete cur;
                m_size--;
                return true;
            }
            prev = cur;
            cur = cur->m_next;
        }
        return false;
    }
}

#endif // !__HASH_TABLE_HPP__
